package leetcode_900;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *LengthOfLongestFibonacciSubsequence_873  计算一个数组里最长斐波拉契序列长度
 *describe:用动态规划 二维数组规划
 *2018年11月7日 下午12:15:32
 */
public class LengthOfLongestFibonacciSubsequence_873 {
	public static void main(String[] args) {
		LengthOfLongestFibonacciSubsequence_873 test=new LengthOfLongestFibonacciSubsequence_873();
		System.out.println(test.lenLongestFibSubseq(new int[] {1,2,3,4,5,6,7,8}));
	}
	
	
	public int lenLongestFibSubseq(int[] A) {
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<A.length;++i) {
        	map.put(A[i], i);//因为A是严格递增的
        }
        
        int dp[][]=new int[A.length][A.length];//dp[i][j]表示以A[i]A[j]结尾的序列的最长长度
        int res=0;
        dp[0][1]=2;
        for(int i=2;i<A.length;++i) {
        	for(int j=0;j<i;++j) {//j是倒数 第2个值
        		if(dp[j][i]==0) dp[j][i]=2;//初始化
        		int need=A[i]-A[j];
        		if(need<=A[j]) {//need应该比A[j]要大
        			continue;
        		}
        		Integer k=map.get(need);
        		if(k==null)
        			continue;
        		//否则map里是有的  i>k>j
        		dp[k][i]=dp[j][k]+1;
        		res=Math.max(res, dp[k][i]);
        	}
        }
        return res>2?res:0;
    }
}
